연역 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 연역의 예시
- 2.1. 삼단논법
3. 추론의 가상 규칙
4. 연역 메타 정리를 사용한 증명에서 공리적 증명으로의 변환
- 4.1. 공리 도식
5. 변환의 예시
- 5.1. 커리-하워드 대응
6. 일차 논리에서의 연역 정리
- 6.1. 양화사 공리
7. 귀납 정리
참조

1. 개요

연역 정리는 어떤 명제 집합(T)과 명제 F를 전제로 하여 G를 증명할 수 있다면, T만으로 F → G를 증명할 수 있다는 정리이다. 연역 정리의 대표적인 예시로 삼단논법이 있으며, 가설, 반복, 연역과 같은 가상 추론 규칙을 사용하여 공리적 증명으로 변환할 수 있다. 일차 논리에서도 연역 정리가 유효하며, 닫힌 논리식 F에 대한 제약 조건이 존재한다. 연역 정리는 귀납 정리의 역이다.

더 읽어볼만한 페이지

연역 - 마음
마음은 의식, 사고, 지각, 감정, 동기, 행동, 기억, 학습 등을 포괄하는 심리적 현상과 능력의 총체이며, 다양한 분야에서 연구되고 인간 삶의 중추적인 역할을 한다.
연역 - 통계적 추론
통계적 추론은 표본 데이터를 통해 모집단에 대한 결론을 도출하는 방법론으로, 추정과 가설 검정을 포함하며, 다양한 접근 방식과 통계 모델을 기반으로 여러 분야에서 활용된다.
수학기초론 정리 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2^κ > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.
논리학 - 모순
모순은 논리학, 철학, 과학 등 다양한 분야에서 사용되는 개념으로, 서로 상반되는 두 가지 주장이나 사실이 동시에 존재하는 상태를 의미하며, 특히 헤겔과 마르크스의 변증법적 유물론에서 사물의 내재적 대립으로서 역사 발전의 원동력으로 간주된다.
논리학 - 특수
특수는 철학에서는 개별적이고 구체적인 존재를, 언어학에서는 눈에 띄는 또는 예외적인 의미를 가지며, 사회적으로 특별함이 중요하게 여겨지기도 한다.

연역 정리

2. 연역의 예시

연역의 대표적인 예시로는 삼단논법이 있다. 삼단논법은 대전제, 소전제, 결론의 세 단계로 구성되며, 전제들이 참이면 결론도 반드시 참이 되는 논증 방식이다.

삼단논법의 예시는 다음과 같다.

「증명」 공리 1:

*''P'' 　1. 가설
**''Q'' 　2. 가설
**''P'' 　3. 1의 반복
*''Q''→''P'' 　4. 2에서 3으로의 연역
''P''→(''Q''→''P'') 　5. 1에서 4로의 연역 QED

「증명」 공리 2:

*''P''→(''Q''→''R'') 　1. 가설
**''P''→''Q'' 　2. 가설

''P'' 　3. 가설
''Q'' 　4. 3과 2에 의한 모두스 포넨스
''Q''→''R'' 　5. 3과 1에 의한 모두스 포넨스
''R'' 　6. 4와 5에 의한 모두스 포넨스

**''P''→''R'' 　7. 3에서 6으로의 연역
*(''P''→''Q'')→(''P''→''R'') 　8. 2에서 7으로의 연역
(''P''→(''Q''→''R''))→((''P''→''Q'')→(''P''→''R'')) 　9. 1에서 8으로의 연역 QED

공리 1을 사용하여 ((''P''→(''Q''→''P''))→''R'')→''R''을 보임:

*(''P''→(''Q''→''P''))→''R'' 　1. 가설
*''P''→(''Q''→''P'') 　2. 공리 1
*''R'' 　3. 2와 1에 의한 모두스 포넨스
((''P''→(''Q''→''P''))→''R'')→''R'' 　4. 1에서 3으로의 연역 QED

2. 1. 삼단논법

삼단논법의 예시는 다음과 같다.

「증명」 공리 1:

*''P'' 　1. 가설
**''Q'' 　2. 가설
**''P'' 　3. 1의 반복
*''Q''→''P'' 　4. 2에서 3으로의 연역
''P''→(''Q''→''P'') 　5. 1에서 4로의 연역 QED

「증명」 공리 2:

*''P''→(''Q''→''R'') 　1. 가설
**''P''→''Q'' 　2. 가설

''P'' 　3. 가설
''Q'' 　4. 3과 2에 의한 모두스 포넨스
''Q''→''R'' 　5. 3과 1에 의한 모두스 포넨스
''R'' 　6. 4와 5에 의한 모두스 포넨스

**''P''→''R'' 　7. 3에서 6으로의 연역
*(''P''→''Q'')→(''P''→''R'') 　8. 2에서 7으로의 연역
(''P''→(''Q''→''R''))→((''P''→''Q'')→(''P''→''R'')) 　9. 1에서 8으로의 연역 QED

공리 1을 사용하여 ((''P''→(''Q''→''P''))→''R'')→''R''을 보임:

*(''P''→(''Q''→''P''))→''R'' 　1. 가설
*''P''→(''Q''→''P'') 　2. 공리 1
*''R'' 　3. 2와 1에 의한 모두스 포넨스
((''P''→(''Q''→''P''))→''R'')→''R'' 　4. 1에서 3으로의 연역 QED

3. 추론의 가상 규칙

예시에서 볼 수 있듯이, 일반적인 공리적 논리에 세 가지 가상(또는 추가적이고 임시적인) 추론 규칙이 추가되었다. 이것들은 "가설", "반복", 그리고 "연역"이다. 일반적인 추론 규칙(예: 전건 긍정과 다양한 공리)은 여전히 사용 가능하다.^[5]^[6]

1. '''가설'''은 이미 사용 가능한 것들에 추가적인 전제를 추가하는 단계이다. 따라서, 이전 단계 ''S''가 다음과 같이 유도되었다면:

: $E_1, E_2, ... , E_{n-1}, E_n \vdash S,$

다른 전제 ''H''를 추가하여 다음과 같이 얻을 수 있다:

: $E_1, E_2, ... , E_{n-1}, E_n, H \vdash H.$

이것은 들여쓰기 수준을 ''n''번째에서 ''n''+1번째로 이동하고 다음과 같이 표시한다.

::::*''S'' 이전 단계

::::**''H'' 가설

2. '''반복'''은 이전 단계를 다시 사용하는 단계이다. 실제로 이것은 가장 최근의 가설이 아닌 가설을 가져와서 연역 단계 이전의 최종 단계로 사용하려는 경우에만 필요하다.

3. '''연역'''은 가장 최근의 가설(여전히 사용 가능)을 제거하고 이전 단계에 접두사로 붙이는 단계이다. 이것은 다음과 같이 한 수준 들여쓰기를 취소하여 표시한다.

:::::*''H'' 가설

:::::*......... (다른 단계)

:::::*''C'' (''H''에서 도출된 결론)

::::*''H''→''C'' 연역

3. 1. 가설

가설은 증명 과정에서 임시로 추가하는 전제이다.^[5]^[6] 이미 사용 가능한 전제에 추가적인 전제를 더하는 것이다. 이전 단계 ''S''가 다음과 같이 연역되었다고 가정한다.

:

E_1, E_2, ... , E_{n-1}, E_n \vdash S

그리고, 여기에 새로운 전제 ''H''를 더하면 다음과 같아진다.

:

E_1, E_2, ... , E_{n-1}, E_n, H \vdash H

이를 기호적으로 나타내면, n번째 들여쓰기에서 n+1번째 들여쓰기가 된다.

3. 2. 반복

반복은 이전에 사용된 단계를 다시 사용하는 것이다. 실제로 이것은 가장 최근의 가설이 아닌 가설을 가져와서 연역 단계 이전의 최종 단계로 사용하려는 경우에만 필요하다.

3. 3. 연역

연역은 가설을 제거하고 이전 단계에 접두사로 붙이는 단계이다.^[5]^[6] 일반적인 공리적 논리에 "가설", "반복", "연역"과 같은 가상 추론 규칙이 추가된다. 일반적인 추론 규칙(예: 전건 긍정)과 다양한 공리도 여전히 사용 가능하다.

가설은 이미 사용 가능한 것들에 추가적인 전제를 추가하는 단계이다. 이전 단계 ''S''가 다음과 같이 유도되었다면:

::

E_1, E_2, ... , E_{n-1}, E_n \vdash S,

다른 전제 ''H''를 추가하여 다음과 같이 얻을 수 있다.

::

E_1, E_2, ... , E_{n-1}, E_n, H \vdash H.

이것은 들여쓰기 수준을 ''n''번째에서 ''n''+1번째로 이동한다.

반복은 이전 단계를 다시 사용하는 단계이다.

연역은 가장 최근의 가설을 제거하고 이전 단계에 접두사로 붙이는 단계이다. 이것은 들여쓰기를 한 수준 취소한다.

4. 연역 메타 정리를 사용한 증명에서 공리적 증명으로의 변환

명제 논리의 공리적 버전에서는 일반적으로 다음 공리 도식을 갖는다. 여기서 ''P'', ''Q'', ''R''은 임의의 명제로 대체된다.

공리 1은: ''P''→(''Q''→''P'')
공리 2는: (''P''→(''Q''→''R''))→((''P''→''Q'')→(''P''→''R''))
모두스 포넨스는: ''P''와 ''P''→''Q''에서 ''Q''를 추론한다.

이러한 공리 도식은 연역 정리를 쉽게 도출할 수 있도록 선택되었다. 따라서 질문을 회피하는 것처럼 보일 수 있다. 그러나 이는 진리표를 사용하여 타우톨로지이고 모두스 포넨스가 진리를 보존하는지 확인하여 정당화될 수 있다.

이러한 공리 도식에서 ''P''→''P''(함축의 반사성) 정리 도식을 빠르게 추론할 수 있으며, 이는 아래에서 사용된다.

# (''P''→((''Q''→''P'')→''P''))→((''P''→(''Q''→''P''))→(''P''→''P''))는 공리 도식 2에서 ''P'', (''Q''→''P''), ''P''를 사용하여 유도된다.

# ''P''→((''Q''→''P'')→''P'')는 공리 도식 1에서 ''P'', (''Q''→''P'')를 사용하여 유도된다.

# (''P''→(''Q''→''P''))→(''P''→''P'')는 단계 2와 단계 1에 모두스 포넨스를 적용하여 유도된다.

# ''P''→(''Q''→''P'')는 공리 도식 1에서 ''P'', ''Q''를 사용하여 유도된다.

# ''P''→''P''는 단계 4와 단계 3에 모두스 포넨스를 적용하여 유도된다.

Γ와 ''H''가 함께 ''C''를 증명하고, Γ가 ''H''→''C''를 증명하는 것을 보여주려고 한다고 가정해 보자. Γ의 전제(재진술 단계) 또는 공리인 추론의 각 단계 ''S''에 대해, 공리 1, ''S''→(''H''→''S'')에 모두스 포넨스를 적용하여 ''H''→''S''를 얻을 수 있다. 단계가 ''H'' 자체(가설 단계)이면, 정리 도식을 적용하여 ''H''→''H''를 얻는다. 단계가 ''A''와 ''A''→''S''에 모두스 포넨스를 적용한 결과인 경우, 먼저 이들이 ''H''→''A''와 ''H''→(''A''→''S'')로 변환되었는지 확인한 다음 공리 2, (''H''→(''A''→''S''))→((''H''→''A'')→(''H''→''S''))를 취하고 모두스 포넨스를 적용하여 (''H''→''A'')→(''H''→''S'')를 얻은 다음 다시 적용하여 ''H''→''S''를 얻는다. 증명의 마지막에는 필요한 경우 ''H''→''C''가 있게 되지만, 이제는 ''H''가 아닌 Γ에만 의존한다. 따라서 추론 단계는 사라지고 ''H''에서 파생된 결론인 이전 단계로 통합된다.

결과 증명의 복잡성을 최소화하기 위해, 변환 전에 몇 가지 전처리가 수행되어야 한다. 결론을 제외하고 실제로 ''H''에 의존하지 않는 단계는 가설 단계 앞으로 이동하고 한 수준 들여쓰기가 해제되어야 한다. 또한, 결론을 얻는 데 사용되지 않거나 우회될 수 있는 재진술과 같이 불필요한 다른 단계도 제거해야 한다.

변환하는 동안, 모두스 포넨스를 공리 1에 적용한 모든 것을 추론의 시작 부분(''H''→''H'' 단계 바로 뒤)에 넣는 것이 유용할 수 있다.

모두스 포넨스를 변환할 때, ''A''가 ''H''의 범위 밖에 있으면, 공리 1, ''A''→(''H''→''A'')를 적용하고 모두스 포넨스를 적용하여 ''H''→''A''를 얻어야 한다. 마찬가지로, ''A''→''S''가 ''H''의 범위 밖에 있으면, 공리 1, (''A''→''S'')→(''H''→(''A''→''S''))를 적용하고 모두스 포넨스를 적용하여 ''H''→(''A''→''S'')를 얻는다. 두 단계를 모두 수행할 필요는 없을 것이다. 즉, 모두스 포넨스 단계가 결론인 경우를 제외하고는, 둘 다 범위 밖에 있다면, 모두스 포넨스는 ''H'' 앞으로 이동되었을 것이고 따라서 범위 밖에 있을 것이다.

커리-하워드 대응에 따라, 추론 메타 정리에 대한 위 변환 과정은 람다 계산법 항에서 결합 논리 항으로의 변환 과정과 유사하며, 여기서 공리 1은 K 조합자에 해당하고 공리 2는 S 조합자에 해당한다. I 조합자는 정리 도식 ''P''→''P''에 해당한다는 점에 유의하십시오.

4. 1. 공리 도식

공리 도식으로 다음을 사용하는 것이 일반적이다 (여기서, ''P'', ''Q'', ''R''은 임의의 명제).

공리 1 : ''P''→(''Q''→''P'')
공리 2 : (''P''→(''Q''→''R''))→((''P''→''Q'')→(''P''→''R''))
모두스 포넨스 : ''P''와 ''P''→''Q''로부터 ''Q''를 추론한다.

이러한 공리로부터 ''P''→''P''가 얻어진다 (명제 논리 참조). 간편함을 위해 정리 ''P''→''P''도 공리 도식으로 채택하기로 한다. 이러한 공리 도식은, 연역 정리가 쉽게 유도될 수 있도록 선택되었다.

직관주의 명제 논리의 함의 단편의 완전한 증명 계산 체계이다.

5. 변환의 예시

자연 연역을 공리적 증명 형식으로 변환하는 과정을 보여주기 위해 항진 명제 ''Q''→((''Q''→''R'')→''R'')을 사용한다. 변환이 가능한지 확인하기 위해 이것으로 충분하다. 이것을 먼저 자연 연역으로 증명하고, 그것을 더 긴 공리적 증명으로 변환한다.

첫째, 자연 연역적 기법으로 증명을 작성한다.

*''Q'' 　1. 가설
**''Q''→''R'' 　2. 가설
**''R'' 　3. 1,2에 의한 모더스 포넨스
*(''Q''→''R'')→''R'' 　4. 2에서 3으로의 연역
''Q''→((''Q''→''R'')→''R'') 　5. 1에서 4로의 연역 QED

둘째, 내부 연역을 공리적 증명으로 변환한다.

(''Q''→''R'')→(''Q''→''R'') 　1. 공리 도식 (''A''→''A'')
((''Q''→''R'')→(''Q''→''R''))→(((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R'')) 　2. 공리 2
((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R'') 　3. 1,2에 의한 모더스 포넨스
''Q''→((''Q''→''R'')→''Q'') 　4. 공리 1
*''Q'' 　5. 가설
*(''Q''→''R'')→''Q'' 　6. 5,4에 의한 모더스 포넨스
*(''Q''→''R'')→''R'' 　7. 6,3에 의한 모더스 포넨스
''Q''→((''Q''→''R'')→''R'') 　8. 5에서 7로의 연역 QED

셋째, 외부 연역을 공리적 증명으로 변환한다.

(''Q''→''R'')→(''Q''→''R'') 　1. 공리 도식 (''A''→''A'')
((''Q''→''R'')→(''Q''→''R''))→(((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R'')) 　2. 공리 2
((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R'') 　3. 1,2에 의한 모더스 포넨스
''Q''→((''Q''→''R'')→''Q'') 　4. 공리 1
[((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R'')]→[''Q''→(((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R''))] 　5. 공리 1
''Q''→(((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R'')) 　6. 3,5에 의한 모더스 포넨스
[''Q''→(((''Q''→''R'')→''Q'')→((''Q''→''R'')→''R''))]→([''Q''→((''Q''→''R'')→''Q'')]→[''Q''→((''Q''→''R'')→''R''))]) 　7. 공리 2
[''Q''→((''Q''→''R'')→''Q'')]→[''Q''→((''Q''→''R'')→''R''))] 　8. 6,7에 의한 모더스 포넨스
''Q''→((''Q''→''R'')→''R'')) 　9. 4,8에 의한 모더스 포넨스 QED

5. 1. 커리-하워드 대응

자연 연역을 공리적 증명 형식으로 변환하는 과정은 커리-하워드 대응을 사용하여 간결하게 표현할 수 있다. 예를 들어 람다 계산에서 함수 f = λa. λb. b a의 타입은 ''q'' → (''q'' → ''r'') → ''r''이며, b에 대한 람다 제거를 통해 f = λa. s i (k a)로, a에 대한 람다 제거를 통해 f = s (k (s i)) k로 표현할 수 있다. 이는 항진 명제 ''Q''→((''Q''→''R'')→''R'')를 사용하여 자연 연역을 공리적 증명으로 변환하는 과정을 보여주는 예시이다.

6. 일차 논리에서의 연역 정리

일차 논리에서도 연역 정리가 유효하다. ''T''가 이론이고, ''F'', ''G''가 논리식이며, ''F''가 닫혀 있고, $T \cup \{ F \} \vdash G$ 이면, $T \vdash F \rightarrow G$ 이다.^[8] 여기서 기호 $\vdash$ 는 "의 구문론적 결과이다"를 의미한다.^[8]

명제 계산의 공리 도식(또는 명제 계산의 모든 항진명제가 그 자체로 공리 도식으로 간주된다는 이해) 외에도, 양화사 공리가 있으며, 추론 규칙인 전건긍정의 원리 외에도 ''일반화'' 규칙이 하나 더 있다.^[8] 즉, ''K''에서 ∀''vK''를 추론한다.^[8]

일반화 규칙의 적용으로 인한 단계는 다음과 같은 양화사 공리를 통해 처리된다(변수 ''v''가 논리식 ''H''에 자유롭게 나타나지 않을 때 유효하다).^[8]

(∀''v''(''H''→''K''))→(''H''→∀''vK'').

''F''는 닫혀 있다고 가정하므로, ''H''를 ''F''로 사용할 수 있다.^[8] 이 공리를 통해 ''F''→''K''와 일반화로부터 ''F''→∀''vK''를 추론할 수 있다.^[8]

일차 논리에서 F가 닫힌 논리식이라는 제약 조건은 F의 자유 변수가

T \cup \{ F \}

에서 G를 연역하는 과정에서 변경되지 않은 경우 완화될 수 있다.^[8] F의 자유 변수 v가 연역 과정에서 변경된 경우,

T \cup \{ F \} \vdash^v G

라고 표기하고(턴스타일에 있는 위첨자는 v가 변경되었음을 나타냄) 이에 해당하는 연역 정리의 형태는

T \vdash (\forall vF) \rightarrow G

이다.^[8]

6. 1. 양화사 공리

7. 귀납 정리

'''귀납 정리'''는 연역 정리의 역이다. 함의 제거 규칙인 모두스 포넨스에서 즉시 유도할 수 있다.

참조

_[1] 서적 Kleene 1967
_[2] 문서 Hilbert-style deductive systems, natural deduction, the sequent calculus, the Method of analytic tableaux|tableaux method, and Resolution (logic)|resolution
_[3] 기타 https://github.com/g[...]
_[4] 서적 Kohlenbach 2008
_[5] 서적 Symbolic Logic: an Introduction https://archive.org/[...] 1952
_[6] 간행물 Types of proof system http://www.logicmatt[...] 2010-10-13
_[7] 기타 Deduction theorem, from Curtis Franks at the University of Notre Dame https://www3.nd.edu/[...] 2020-07-21
_[8] 서적 Introduction to meta-mathematics North Holland

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com